package 数据结构与算法.实验三;

import java.util.Stack;

public class StackMaze {
    static int[][] matrix;

    public static void main(String[] args) {
        matrix = new int[][]{
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
                {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
                {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
                {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
                {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
                {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
                {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
        };
        Stack<int[]> stack = new Stack<>();
        int[] x = {-1, 1, 0, 0};
        int[] y = {0, 0, -1, 1};
        stack.push(new int[]{1, 1});
        matrix[1][1] = 2;
        printResult();
        while (!stack.isEmpty()) {
            int[] cur = stack.peek();
            if (cur[0] == 8 && cur[1] == 8) {
                printResult();
                break;
            }
            int i;
            for (i = 0; i < 4; i++) {
                int row = cur[0]+x[i];
                int column = cur[1]+y[i];

                if (matrix[row][column] == 0) {
                    stack.push(new int[]{row, column});
                    matrix[row][column] = 2;
                    break;
                }
            }
            if (i == 4) {
                cur = stack.pop();
                matrix[cur[0]][cur[1]] = -1;
            }
        }
    }

    public static void printResult() {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] == 2){
                    System.out.print("[" + i + "," + j + "] ");
                }
            }
        }
    }
}
